package com.kuang.linkedlist;

/*给你一个链表的头节点 head ，判断链表中是否有环。
        用 O(1)（即，常量）内存解决此问题*/

/**
 * @author kjx
 */
public class HasCycle {


    //第一种思路，也是最简单的思路，就是把每个链表的哈希值给存下来，然后遍历的时候去查找一下就行
    //但是这种思路没啥意义，就不做演示了；
    //用快慢双指针来做
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode fastPtr = head;
        ListNode slowPtr = head;
        while (fastPtr.next != null && fastPtr.next.next != null) {
            fastPtr = fastPtr.next.next;
            slowPtr = slowPtr.next;
            if (fastPtr == slowPtr) {
                return true;
            }
        }
        return false;
    }
}
